// https://www.lintcode.com/problem/classical-binary-search/

class Solution {
public:
    /**
     * @param nums: An integer array sorted in ascending order
     * @param target: An integer
     * @return: An integer
     */
    int findPosition(vector<int> &nums, int target) {
        if (nums.empty()) return -1;
        int start = 0;
        int end = nums.size() - 1;
        while (start + 1 < end)
        {
            int mid = (end - start) / 2 + start;
            if (nums[mid] == target)
            {
                return mid;
            }
            if (nums[mid] > target)
            {
                end = mid;
            }
            else
            {
                start = mid;
            }
        }
        if (nums[start] == target) return start;
        if (nums[end] == target) return end;
        return -1;
    }
};